package binary_tree.leetcode.easy;

import java.util.*;

/**
 * @author Stark
 * @description 二叉树的中序遍历
 * 题目链接：https://leetcode-cn.com/problems/binary-tree-inorder-traversal
 * @date 2022/4/14 13:33
 **/
public class Num94_InorderTraversal {
    int choice = 1;
    List<Integer> list = new ArrayList<>();
    public List<Integer> inorderTraversal(TreeNode root) {
        if (choice == 1) {
            //递归法
            if (root == null)
                return list;
            inorderTraversal(root.left);
            list.add(root.val);
            inorderTraversal(root.right);
            return list;
        } else if (choice == 2) {
            //非递归法
            if(root == null){
                return list;
            }
            Deque<TreeNode> stack = new ArrayDeque<>();
            TreeNode node = root;
            //初始栈为空，因为不能存入结点
            //进入循环需要加上node != null
            while(node != null || !stack.isEmpty()){
                //一直往左子树走到底
                while(node != null){
                    stack.push(node);
                    node = node.left;
                }
                node = stack.pop();
                list.add(node.val);
                //往右结点走,处理右结点
                node = node.right;
            }
            return list;
        }
        return null;
    }
}
